/*
 * @lc app=leetcode.cn id=1035 lang=golang
 *
 * [1035] 不相交的线
 */
package Solutions

// @lc code=start
func maxUncrossedLines(nums1 []int, nums2 []int) int {
	var dp = make([][]int, 0, len(nums1)+1)
	for i := 0; i < len(nums1)+1; i++ {
		dp = append(dp, make([]int, len(nums2)+1))
	}
	var max = func(a, b int) int {
		if a < b {
			return b
		}
		return a
	}
	for i := 0; i < len(nums1); i++ {
		var maxLines = 0
		for j := 0; j < len(nums2); j++ {
			if nums1[i] == nums2[j] {
				dp[i+1][j+1] = dp[i][j] + 1
				maxLines = max(dp[i+1][j+1], maxLines)
			} else {
				dp[i+1][j+1] = max(maxLines, dp[i][j+1])
			}
		}
	}
	return dp[len(nums1)][len(nums2)]
}

// @lc code=end
